1. Identificação | |
Tipo de Referência | Artigo em Revista Científica (Journal Article) |
Site | plutao.sid.inpe.br |
Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
Identificador | 8JMKD3MGP3W/3TEPCS5 |
Repositório | sid.inpe.br/plutao/2019/06.10.14.29 (acesso restrito) |
Última Atualização | 2019:06.14.10.21.50 (UTC) lattes |
Repositório de Metadados | sid.inpe.br/plutao/2019/06.10.14.29.01 |
Última Atualização dos Metadados | 2020:01.06.11.35.23 (UTC) administrator |
DOI | 10.1016/j.asoc.2019.105482 |
ISSN | 1568-4946 |
Rótulo | lattes: 0096913881679975 3 ChagasLoreSant:2019:HyHeOv |
Chave de Citação | ChagasLoreSant:2019:HyHeOv |
Título | A hybrid heuristic for the overlapping cluster editing problem |
Ano | 2019 |
Data de Acesso | 12 maio 2024 |
Tipo de Trabalho | journal article |
Tipo Secundário | PRE PI |
Número de Arquivos | 1 |
Tamanho | 806 KiB |
|
2. Contextualização | |
Autor | 1 Chagas, Guilherme Oliveira 2 Lorena, Luiz Antonio Nogueira 3 Santos, Rafael Duarte Coelho dos |
Identificador de Curriculo | 1 2 8JMKD3MGP5W/3C9JHMQ 3 8JMKD3MGP5W/3C9JJ4N |
Grupo | 1 LABAC-COCTE-INPE-MCTIC-GOV-BR 2 LABAC-COCTE-INPE-MCTIC-GOV-BR 3 LABAC-COCTE-INPE-MCTIC-GOV-BR |
Afiliação | 1 Instituto Nacional de Pesquisas Espaciais (INPE) 2 Instituto Nacional de Pesquisas Espaciais (INPE) 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
Endereço de e-Mail do Autor | 1 guilherme.chagas@inpe.br 2 3 rafael.santos@inpe.br |
Revista | Applied Soft Computing |
Volume | 81 |
Páginas | 105482 |
Nota Secundária | A2_INTERDISCIPLINAR A2_ENGENHARIAS_IV A2_ENGENHARIAS_III A2_CIÊNCIA_DA_COMPUTAÇÃO B1_MATEMÁTICA_/_PROBABILIDADE_E_ESTATÍSTICA B1_ENGENHARIAS_II B1_BIOTECNOLOGIA |
Histórico (UTC) | 2019-06-10 14:29:01 :: lattes -> administrator :: 2019-06-10 14:43:22 :: administrator -> lattes :: 2019 2019-06-14 10:21:51 :: lattes -> administrator :: 2019 2020-01-06 11:35:23 :: administrator -> simone :: 2019 |
|
3. Conteúdo e estrutura | |
É a matriz ou uma cópia? | é a matriz |
Estágio do Conteúdo | concluido |
Transferível | 1 |
Tipo do Conteúdo | External Contribution |
Tipo de Versão | publisher |
Palavras-Chave | Overlapping cluster editing Cluster editing Overlapping clustering Hybrid heuristic |
Resumo | Clustering problems are applicable to several areas of science. Approaches and algorithms are as varied as the applications. From a graph theory perspective, clustering can be generated by partitioning an input graph into a vertex-disjoint union of cliques (clusters) through addition and deletion of edges. Finding the minimum number of edges additions and deletions required to cluster data that can be represented as graphs is a well-known problem in combinatorial optimization, often referred to as cluster editing problem. However, many real-world clustering applications are characterized by overlapping clusters, that is, clusters that are non-disjoint. In these situations cluster editing cannot be applied to these problems. Literature concerning a relaxation of the cluster editing, where clusters can overlap, is scarce. In this work, we propose the overlapping cluster editing problem, a variation of the cluster editing where the goal is to partition a graph, also by editing edges, into maximal cliques that are not necessarily disjoint. In addition, we also present three slightly different versions of a hybrid heuristic to solve this problem. Each hybrid heuristic is based on coupling two metaheuristicsthat, together, generate a set of clusters; and one of three mixed-integer linear programming models, also introduced in this paper, that uses these clusters as input. The objective with the metaheuristics is to limit the solution exploration space in the models resolution, therefore reducing its computational time. Tests results show that the all proposed hybrid heuristic versions are able to generate good-quality overlapping cluster editing solutions. In particular, one version of the hybrid heuristic achieved, at a low computational cost, the best results in 51 of 112 randomly-generated graphs. Although the other two hybrid heuristic versions have harder to solve models, they obtained reasonable results in medium-sized randomly-generated graphs. In addition, the hybrid heuristic achieved good results identifying labeled overlapping clusters in a supervised data set experiment. Furthermore, we also show that, with our new problem definition, clustering a vertex in more than one cluster can reduce the edges editing cost. |
Área | COMP |
Arranjo | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > A hybrid heuristic... |
Conteúdo da Pasta doc | acessar |
Conteúdo da Pasta source | não têm arquivos |
Conteúdo da Pasta agreement | não têm arquivos |
|
4. Condições de acesso e uso | |
Idioma | en |
Arquivo Alvo | 1-s2.0-S1568494619302522-main.pdf |
Grupo de Usuários | lattes |
Grupo de Leitores | administrator lattes |
Visibilidade | shown |
Política de Arquivamento | denypublisher denyfinaldraft24 |
Permissão de Leitura | deny from all and allow from 150.163 |
Permissão de Atualização | não transferida |
|
5. Fontes relacionadas | |
Unidades Imediatamente Superiores | 8JMKD3MGPCW/3ESGTTP |
Lista de Itens Citando | sid.inpe.br/mtc-m21/2012/07.13.14.54.04 2 sid.inpe.br/mtc-m21/2012/07.13.14.58.32 1 sid.inpe.br/bibdigital/2013/09.22.23.14 1 |
Divulgação | WEBSCI; PORTALCAPES; COMPENDEX. |
Acervo Hospedeiro | dpi.inpe.br/plutao@80/2008/08.19.15.01 |
|
6. Notas | |
Campos Vazios | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel e-mailaddress format isbn lineage mark mirrorrepository month nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress project rightsholder schedulinginformation secondarydate secondarykey session shorttitle sponsor subject tertiarymark tertiarytype url |
|
7. Controle da descrição | |
e-Mail (login) | simone |
atualizar | |
|